package other;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class D230904 {
    // 主持人调度(二)

    // 时间：O(nlog(2)n)    排序是 O(nlog(2)n)   遍历是 O(n)  遍历中维护是 O(log(2)n)
    // 空间：O(n)
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // 使用 Arrays.sort 对数组排序
        // 按开始时间进行，递增排序
        Arrays.sort(startEnd, new Comparator<Object>() {
            public int compare(Object o1, Object o2) {
                int[] one = (int []) o1;
                int[] two = (int []) o2;
                if (one[0] > two[0]) {
                    return 1;
                } else if (one[0] < two[0]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        // 小顶堆，优先级队列，队列中存放活动的结束时间，按从小到大排序
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        // 可能有负区间（队列中设置初始值）
        q.offer(Integer.MIN_VALUE);
        for(int i = 0; i < n; i++){

            if(q.peek() <= startEnd[i][0])
                // 最近的活动结束时间 小于 当前活动开始时间
                q.poll(); // 出队（时间没有冲突）

            q.offer(startEnd[i][1]); // 入队（当前活动的结束时间）
        }
        // 剩余的活动等于主持人数
        return q.size();
    }
}
